package basic.courseLearn03.sort;

import basic.courseLearn01.utils.FunctionSort;
import basic.courseLearn01.utils.SortUtils;
import org.junit.Test;

public class RadixSort implements FunctionSort {
    @Override
    public int[] sort(int[] result) {
        return radixSort(result);
    }

    @Test
    public void test(){
//        int[] arr = new int[]{12,313,210,10,200,1};
//        arr=radixSort(arr);
//        System.out.println(CommonUtil.printArray(arr));
        SortUtils.executeCheckAlgorithm(1_0000,1000,1000,this);
    }

    //基数排序(从小到大)
    public int[] radixSort(int[] arr){
        int[] tempBucket = new int[10];
        int digit = calMaxDigit(arr);
        for (int i = 1; i <= digit; i++) {
            tempBucket = initEmptyArray(tempBucket);
            int[] tempArray = new int[arr.length];
            //入桶
            for (int j = 0; j < arr.length; j++) {
                tempBucket[calDigitIndex(arr[j],i)]++;
            }
            int tempData = tempBucket[0];
            //前缀和
            for (int j = 1; j < tempBucket.length; j++) {
                tempBucket[j]+=tempData;
                tempData=tempBucket[j];
            }
            //出桶
            for (int j = arr.length-1; j >= 0 ; j--) {
                tempArray[tempBucket[calDigitIndex(arr[j],i)]-1]=arr[j];
                tempBucket[calDigitIndex(arr[j],i)]-=1;
            }
            arr = tempArray;
        }
        return arr;
    }

    //初始化全部为零的数组
    public static int[] initEmptyArray(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            arr[i]=0;
        }
        return arr;
    }

    //计算最高位
    public static int calMaxDigit(int[] arr){
        int max = arr[0],digit=0;
        for (int i = 1; i < arr.length; i++) {
            if (max<arr[i]){
                max=arr[i];
            }
        }
        while(max!=0){
            digit++;
            max/=10;
        }
        return digit;
    }

    //获取一个数第几位的数，123--个十百
    public static int calDigitIndex(int num,int index){
        int res=0;
        while(index>0){
            res = num%10;
            num/=10;
            index--;
        }
        return res;
    }

}
